package com.lht.leetcodeDemo;

import org.junit.Test;

/**
 * Leetcode之最长公共前缀
 *
 * @author Eric
 * @version 1.0
 * @date 2019-05-17
 */
public class LongestCommonPrefix {

    /**
     * 测试方法
     *
     * @return void
     * @throws
     * @author Eric
     * @date 2019/5/17
     **/
    @Test
    public void test() {
        System.out.println(new LongestCommonPrefix().longestCommonPrefix(new String[]{"aca", "cba"}));
    }

    /**
     * <p>
     * 我的代码实现
     * </p>
     *
     * @param strArray 字符串数组
     * @return java.lang.String
     * @throws
     * @author Eric
     * @date 2019/5/17
     **/
    public String longestCommonPrefix(String[] strArray) {
        if (strArray.length < 1) {
            return "";
        }
        if (strArray.length < 2) {
            return strArray[0];
        }
        //默认数组第一位第一个公共前缀
        String commonPrefix = strArray[0];
        for (int i = 1; i < strArray.length; i++) {
            StringBuilder s = new StringBuilder();
            //开始和第二个字符串，比较长度，获取到两者短的
            String shortStr = commonPrefix.length() >= strArray[i].length() ? strArray[i] : commonPrefix;
            //for循环两者短的，从0-最短字符串长度，比较两者char是否相同，把相同拼接起来，如果不相同，跳出循环
            for (int j = 0; j < shortStr.length(); j++) {
                if (commonPrefix.charAt(j) != strArray[i].charAt(j)) {
                    break;
                }
                s.append(commonPrefix.charAt(j));
            }
            //将拼接的字符串赋值给公共前缀
            commonPrefix = s.toString();
            //如果公共前缀字符串为”“  return ""
            if ("".equals(commonPrefix)) {
                return commonPrefix;
            }
        }
        return commonPrefix;
    }

    /**
     * <p>
     * 最优秀的算法实现
     * </p>
     *
     * @param strArray 字符串数组
     * @return java.lang.String
     * @throws
     * @author Eric
     * @date 2019/5/17
     **/
    public String smartLongestCommonPrefix(String[] strArray) {
        if (strArray.length == 0) {
            return "";
        }
        //赋值第一个字符串为公共前缀
        String commonPrefix = strArray[0];
        for (int i = 1; i < strArray.length; i++) {
            // 实现核心思路通过第二字符串indexOf(公共前缀字符串)！=0
            while (strArray[i].indexOf(commonPrefix) != 0) {
                //公共前缀长度从后缩短1，再次执行indexOf(),知道！=0，获取公共前缀长度变成0 indexOf() 肯定！=0
                commonPrefix = commonPrefix.substring(0, commonPrefix.length() - 1);
            }
            if ("".equals(commonPrefix)) {
                return commonPrefix;
            }
        }
        //return 公共前缀字符串
        return commonPrefix;

    }

    /**
     * 自己研究下 indexOf() 方法性能为什么这么高
     * Code shared by String and StringBuffer to do searches. The
     * source is the character array being searched, and the target
     * is the string being searched for.
     *
     * @param   source       the characters being searched.  源字符串
     * @param   sourceOffset offset of the source string.    源字符串计算偏移
     * @param   sourceCount  count of the source string.      源码字符串参与计算长度     offset+count  源字符串参与计算的部分
     * @param   target       the characters being searched for.   匹配目标字符串
     * @param   targetOffset offset of the target string.         目标字符串计算偏移量
     * @param   targetCount  count of the target string.           目标字符串参与计算数量
     * @param   fromIndex    the index to begin searching from.   不是太清楚干嘛的 翻译 要开始搜索的索引
     */
    static int indexOf(char[] source, int sourceOffset, int sourceCount,
                       char[] target, int targetOffset, int targetCount,
                       int fromIndex) {
        //如果开始搜索下表 大于 源字符串搜索数，直接返回查找不到，这里猜测下，应该是开始匹配的位置，个人觉得 formIndex 和sourceOffset 应该是相等的
        if (fromIndex >= sourceCount) {
            return (targetCount == 0 ? sourceCount : -1);
        }
        //过滤小于零情况，默认为零
        if (fromIndex < 0) {
            fromIndex = 0;
        }
        //如果查询目标字符串长度为零 ,就是空字符串匹配，返回应该是fromIndex ，正常情况下formIndex 为0 就是source 开始位置
        if (targetCount == 0) {
            return fromIndex;
        }
        //第一个目标字符串
        char first = target[targetOffset];
        //这步看不懂，我应该觉得是 sourceCount+targetCount
        int max = sourceOffset + (sourceCount - targetCount);

        for (int i = sourceOffset + fromIndex; i <= max; i++) {
            /* Look for first character. */
            //标准的kmb 先比较第一个字符串是否相同
            if (source[i] != first) {
                while (++i <= max && source[i] != first){

                };
            }

            /* Found first character, now look at the rest of v2 */
            if (i <= max) {
                int j = i + 1;
                int end = j + targetCount - 1;
                //如果第一个字符相同，开始比较身子是否相同
                for (int k = targetOffset + 1; j < end && source[j]
                        == target[k]; j++, k++){

                };
                //比较结束，比较到最后字符，以为着身子都是相同的
                if (j == end) {
                    /* Found whole string. */
                    return i - sourceOffset;
                }
            }
        }
        return -1;
    }
}
